// https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/
package main

/*
go语言计数排序耗时0ms，超过百分之百的用户！

观察到数据范围并不是很大， 那么可以使用计数排序。
创建长度为 201的数组，存储这些数字的数量，并且按照大小进行排序
反转的时候，将当前位置 - 1， 对应整数位置 +1 即可。（并且优化求 min（k, 当前位置个数））
一次可交换多个负数。

关键在于， 201 长度的数组，表示 -100 到 100 之间的数， 换算不要出错。

-100 存在第一位， 所以 num + 100 是这个数的 下标。
负数对应的正数， 假设下标为 i， i-100 得到当前数字， 取反再 加100得到整数下标：
-1 * (i - 100) + 100
*/

// 观察到数据范围并不是很大， 那么可以使用计数排序
func largestSumAfterKNegations(nums []int, k int) int {
	sortCnt := make([]int, 201)
	// 进行排序
	for _, num := range nums {
		sortCnt[num+100] += 1
	}
	for i, num := range sortCnt {
		// 当前位置没有值，肯定跳出
		if num == 0 {
			continue
		}
		// 1. 如果有负数， 全部转正
		if i < 100 {
			n := min(k, sortCnt[i])
			// 次数减少
			k -= n
			// 对应整数位置加， 该负数位置减掉
			sortCnt[i] -= n
			sortCnt[-1*(i-100)+100] += n
		}
		// 2. 最小正数处理
		if i > 100 {
			// 取最小的正数，将剩下的k次用完
			if k%2 == 1 {
				// 正数位置减掉1个
				sortCnt[i] -= 1
				// 对应负数位置增加1个
				sortCnt[-1*(i-100)+100] += 1
				// 跳出
				break
			}
		}
		// 2. 交换了 K次， 或者是 全部都是正数，此时为 0，那就跳出
		if k == 0 || i == 100 {
			break
		}
	}

	// 4. 求和
	rst := 0
	for i, cnt := range sortCnt {
		if cnt != 0 {
			rst += (i - 100) * cnt
		}
	}
	return rst
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// 评论区 一种java写的 双排序
/*

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        // 排序，把可能有的负数排到前面
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            // 贪心：如果是负数，而k还有盈余，就把负数反过来
            if (nums[i] < 0 && k > 0) {
                nums[i] = -1 * nums[i];
                k--;
            }
            sum += nums[i];
        }
        Arrays.sort(nums);
        // 如果k没剩，那说明能转的负数都转正了，已经是最大和，返回sum
        // 如果k有剩，说明负数已经全部转正，所以如果k还剩偶数个就自己抵消掉，不用删减，如果k还剩奇数个就减掉2倍最小正数。
        return sum - (k % 2 == 0 ? 0 : 2 * nums[0]);
    }
}

*/
